# 背包选取的物品列表
picks = []
picks_wights_idx = []
picks_with_max_value = []
picks_with_max_weight= []




def bag(capcity:int, cur_weight:int, items_weight:list, pick_idx:int):
    """
    固定容量的背包，计算能装进背包的物品组合的最大重量
    回溯法解决01背包，穷举
    时间复杂度O(n^2)
    :param capcity:背包容量
    :param cur_weight:背包当前的重量
    :param items_weight:[物品的重量,....]
    :param pick_idx:当前物品的索引
    :return:
    """
    # 遍历所有的物品或者达到背包容量
    if pick_idx >= len(items_weight) or cur_weight == capcity:
        global picks_with_max_weight
        if get_weight(items_weight, picks_wights_idx) > get_weight(items_weight, picks_with_max_weight):
            picks_with_max_weight = picks_wights_idx.copy()
    else:
        if cur_weight + items_weight[pick_idx] <= capcity:
            picks_wights_idx[pick_idx] = 1
            bag(capcity, cur_weight+items_weight[pick_idx], items_weight, pick_idx+1)

        picks_wights_idx[pick_idx] = 0
        bag(capcity, cur_weight, items_weight, pick_idx+1)


def get_weight(items_weight: list, pick_items: list):
    return sum([a*b for a,b in zip(items_weight, pick_items)])




def bag_with_max_value(capcity:int, cur_weight:int, items_info: list, pick_idx:int):
    """
    固定容量的背包，计算能装进背包的物品组合的最大价值
    回溯法解决01背包，穷举
    时间复杂度O(n^2)
    :param capcity: 背包容量
    :param cur_weight: 背包当前的重量
    :param items_info: [(物品的重量,价值信息),(.,.)....]
    :param pick_idx: 当前物品的索引
    :return:
    """
    # 遍历所有物品或者达到背包容量
    if pick_idx >= len(items_info) or cur_weight == capcity:
        global picks_with_max_value
        if get_value(items_info, picks) > get_value(items_info, picks_with_max_value):
            picks_with_max_value = picks.copy()
    else:
        item_weight = items_info[pick_idx][0]
        if cur_weight + item_weight <= capcity:   #选择
            picks[pick_idx] = 1
            bag_with_max_value(capcity, cur_weight + item_weight, items_info, pick_idx+1)
        picks[pick_idx] = 0  #不选
        bag_with_max_value(capcity, cur_weight, items_info, pick_idx+1)


def get_value(items_info: list, pick_items: list):
    values = [_[1]for _ in items_info]
    return sum([a*b for a, b in zip(values, pick_items)])


def test_bag_with_max_value():
    # [(weight, value), ...]
    items_info = [(3, 5), (2, 2), (1, 4), (2, 2), (4, 10)]
    capacity = 8

    print('--- items info ---')
    print(items_info)

    print('\n--- capacity ---')
    print(capacity)
    global picks
    picks = [0] * len(items_info)
    bag_with_max_value(capacity, 0, items_info, 0)

    print('\n--- picks ---')
    print(picks)

    print('\n--- picks_with_max_value ---')
    print(picks_with_max_value)

    print('\n--- value ---')
    print(get_value(items_info, picks_with_max_value))


def test_bag_with_max_weight():
    items_weight = [3,90,4,5,1]
    capacity = 8
    global picks_wights_idx
    picks_wights_idx = [0] * len(items_weight)
    print('--- items weight ---')
    print(items_weight)

    print('\n--- capacity ---')
    print(capacity)

    bag(capacity, 0, items_weight, 0)

    print('\n picks_with_max_weight')
    print(picks_with_max_weight)


if __name__ == '__main__':
    test_bag_with_max_weight()